import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class TestDemo1B {
    //镜像二叉树
    public void Mirror(TreeNode root){
        if(root==null){
            return ;
        }
        //左右子树交换
        TreeNode tem=root.left;
        root.left=root.right;
        root.right=tem;
        Mirror(root.left);
        Mirror(root.right);
    }

    public ListNode deleteDuplication(ListNode pHead){
        if(pHead==null){
            return null;
        }
        ListNode head=new ListNode(0);
        head.next=pHead;
        ListNode prev=head;
        ListNode last=prev.next;
        while(last!=null){
            //不重复的情况
            while(last.next!=null&&last.val!=last.next.val){
                prev=prev.next;
                last=last.next;
            }
            while(last!=null&&last.val==last.next.val){
                last=last.next;
            }
            if(prev.next!=last){
                prev.next=last.next;
            }
            last=last.next;
        }
        return head.next;
    }

    public ListNode Merge(ListNode list1,ListNode list2){
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }ListNode newHead=new ListNode(0);
        ListNode cur=newHead;
            cur=list1.val>list2.val?list2:list1;
            while(list1!=null&&list2!=null){
                if(list1.val<list2.val){
                    cur.next=list1;
                    cur=cur.next;
                    list1=list1.next;
                }
                else{
                    cur.next=list2;
                    cur=cur.next;
                    list2=list2.next;
                }
            }
        if(list1==null){
            cur.next=list2;
        }
        if(list2==null){
            cur.next=list1;
        }
        return newHead.next;
    }

    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA==null||popA==null||pushA.length!=popA.length){
            return false;
        }
        Stack<Integer>st=new Stack<>();
        int i=0;
        int j=0;
        for(;i<pushA.length;i++){
            st.push(pushA[i]);
            while(!st.empty()&&st.peek()==popA[j]){
                st.pop();
                j++;
            }
        }
        return st.empty();
    }
    public boolean VerifySquenceOfBST1(int [] sequence){
        if(sequence==null){
            return false;
        }
        return VerifySquenceOfBSTCore1(sequence,0,sequence.length-1);
    }

    public boolean VerifySquenceOfBSTCore1(int []sequence,int start,int end){
        if(start>=end){
            return true;
        }
        int root=sequence[end];
        int i=start;
        while(sequence[i]<root){
            i++;
        }
        for(int j=i;i<sequence.length;i++){
            if(root>sequence[j]){
                return false;
            }
        }
        return VerifySquenceOfBSTCore1(sequence,0,i-1)&&
                VerifySquenceOfBSTCore1(sequence,i,end-1);
    }

//输入一个非空整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输
//入的数组的任意两个数字都互不相同。
    public boolean VerifySquenceOfBST(int [] sequence){
        if(sequence==null){
            return false;
        }
       return VerifySquenceOfBSTCore(sequence,0,sequence.length-1);
    }

    public boolean VerifySquenceOfBSTCore(int [] sequence, int start, int end){
        if(start>=end){//左边的下标大于右边的下标说明递归结束
            return true;
        }
        int root=sequence[end];//找到根节点
        int i=start;//起始位置
        while(i<end&&sequence[end]>sequence[i]){//遍历根节点的左树范围
            i++;
        }
        for(int j=i;j<sequence.length;j++){//右树遍历
            if(sequence[j]<sequence[end]){//如果右树范围内有小于根节点的值,直接false
                return false;
            }
        }
        return VerifySquenceOfBSTCore(sequence,start,i-1)&&//左树遍历
                VerifySquenceOfBSTCore(sequence,i,end-1);//右树遍历
    }

//输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点
//开始往下一直到叶结点所经过的结点形成一条路径。
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target){
        ArrayList<ArrayList<Integer>>result=new ArrayList<>();
        ArrayList<Integer>list=new ArrayList<>();
        FindPathDFS(root, target, result, list);
        return result;
    }
    public void FindPathDFS(TreeNode root,int target, ArrayList<ArrayList<Integer>>
            result,ArrayList<Integer> list){
        if(root==null){
            return ;
        }//将当前值放入list中
        list.add(root.val);
        target-= root.val;//更新目标值
        //1. 已经是叶子节点了
        //2. 从root到该叶子节点，之和是target
        //3. 是叶子节点，但是不满足节点，也不影响，程序会直接退出
        if(root.left==null&&root.right==null&&target==0){
            result.add(list);
        }
        FindPathDFS(root.left,target,result,list);
        FindPathDFS(root.right,target,result,list);
        list.remove(list.size()-1);//回退
    }

//输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出
//来的所有字符串 abc,acb,bac,bca,cab 和 cba 。
    public void Swap(char[] str, int i, int j){
        char tem=str[i];
        str[i]=str[j];
        str[j]=tem;
    }
    public boolean IsExist(ArrayList<String> result, char[] str){
        return result.contains(String.valueOf(str));
    }
    public void PermutationHelper(char[] str, int start, ArrayList<String> result){
        if(start==str.length-1){//start走到了结尾
            if(!IsExist(result,str)){//判断里面是否有重复的添加
                result.add(new String(str));
            }
        }
        for(int i=start;i<str.length;i++){
            Swap(str,start,i);//每次都从i下标开始(变成首元素)
            PermutationHelper(str,start+1,result);//(从首元素)的后面开始遍历
            Swap(str,start,i);//恢复一开始的位置
        }
    }
    public ArrayList<String> Permutation(String str) {
        ArrayList<String>result=new ArrayList<>();
        if(str!=null&&str.length()>0){
            PermutationHelper(str.toCharArray(),0,result);
        }
        return result;
    }
}

